1. Field of the Invention
The present invention relates generally to arithmetic and logical shifting of numerical values by a computer microprocessor.
2. Description of Background Art
Numerical shift operations are a standard feature of modern microprocessor code. Shifting is useful for performing multiplication and division operations, as well as for various masking and other operations.
There are two kinds of shifting operations: logical shift and arithmetic shift. As is known by those skilled in the art, a logical shift right of an m-bit binary number by a shift amount n results in a new number having zeros in the n-most significant bits, followed by the (mxe2x88x92n)-most significant bits of the original number. For example, if the number 10011011 is shifted right by 3, the result will be 00010011. Similarly, a logical shift left results in a number consisting of the (mxe2x88x92n)-most significant bits, followed by n zeroes. Thus, when 10011011 is shifted left by 3, the result will be 11011000.
Unlike a logical shift right, an arithmetic shift right preserves the most significant bit of a number when doing the shift. Typically, the most significant bit represents the sign (positive or negative) of the number, and the remaining bits specify the magnitude of the number. If the most significant bit is a 1, i.e., the number is negative, then n 1s are inserted into the most significant bits of the number as it is shifted right. For example, in the example above, an arithmetic shift right by 3 of 10011011 would result in 11110011. Note that if the number is positive, an arithmetic shift right will yield exactly the same result as a logical shift right.
In the past, a commonly used microprocessor instruction was the rotate function, which would rotate a number either right or left. For example, a right rotate by 3 of 10011011 would be 01110011. At present, however, the rotate instruction is not commonly used, and is available mainly as a legacy instruction, providing backward compatibility with older microcode. However, the rotators were and are conventionally used to perform the microcode shift operations.
Because a rotator takes up a relatively large surface area, and because an m-bit rotator requires m wires running from the output back to the input, it was desirable to remove at least one of the rotators while still being able to perform both left and right shift operations. This was made possible by the realization that rotating a binary number x right by some amount r is equivalent to rotating x left by the two""s complement of r. For example, rotating the number 11010010 right by 3 using a left rotator, is equivalent to rotating the number left by 5, which is the two""s complement of 3. Using either method, the result is the same: 01011010. To perform a logical shift using the rotator, zeroes would have to be added either to the most significant bits or least significant bits, for a right or left shift, respectively. And for an arithmetic shift right, ones would have to be added to the most significant bits. Therefore, in addition to the rotator, a masking logic was used to complete the shift operations.
FIG. 1 illustrates a prior art example of a system 100 for performing shifting operations using a left rotator. The system 100 includes a shift amount latch 101, a shift amount 102, a left shift control line 104, a right shift control line 106, a multiplexor 110, two""s complement hardware 112, a multiplexor control line 108, a left rotator 114, a masking logic 116, a rotated data output 118, a shift count 120, shifted data 122, a data latch 124, data 125 to be shifted, and a shift amount input 126. Latch 101 is coupled to the left shift control line 104 and right shift control line 106. Left shift control line 104 is in turn coupled to multiplexor 110. Right shift control line 106 is coupled to two""s complement hardware 112, which is further coupled to multiplexor 110. Multiplexor control line 108 is additionally coupled to multiplexor 110. Multiplexor 110 is further coupled to left rotator 114, which is also coupled to masking logic 116. Masking logic 116 is further coupled to the rotated data output 118 and shift count 120.
A shift amount 102 is input via latch 101. The shift amount 102 is passed through the left shift control line 104 for left shift operations, or through the right shift control line 106 for right shift operations. The multiplexor 110 is also connected to the multiplexor control line 108, and the output channel of the multiplexor 110 is coupled to the input channel of the left rotator 114, which also receives data 125 to be shifted from latch 124. The output channel of the left rotator 114 sends data to masking logic 116. The masking logic output is shifted data 122.
The shift amount 102 is passed either through data line 104 to be shifted left, or data line 106 to be shifted right. The control line 108 controls which input is used by the multiplexor 110, also known as a mux. For any right shift operation, the shift amount 102 is first converted into its two""s complement by the additional two""s complement hardware 112 before reaching the mux 110.
While using two""s complement eliminates the space needed by a second rotator, the operations of determining a two""s complement and performing the masking function are undesirably time consuming and still require a left rotator 114, and a masking logic 116. Therefore, what is needed is a structure and method for performing arithmetic shift right operations that requires less overhead than two""s complement structures and operations, while eliminating the need for a rotator, using a small surface area.
In accordance with the present invention, there is provided a structure and method for performing arithmetic shift right operations by n of an m-bit negative number, where n is less than or equal to m-1. The structure includes left and right shifters, a shift count, a logical OR gate, and conventional data pathways. The shifters are connected to a shift count, and configured to receive data to be shifted. The shifters are additionally coupled to an OR gate, which is in turn connected to an output latch. The right shifter executes a logical shift right operation on the number to be shifted. For example, if an m-bit negative number is to be arithmetically shifted right by n, the right shifter logically shifts the m-bit negative number right by n. Then, the one""s complement of n is determined, and the left shifter performs a left shift on an m-bit mask of ones, left shifting the mask by the one""s complement of n. An OR operation is then performed on the results of the two shifting operations, producing the desired arithmetic shift right result without the need for computing the two""s complement of n.